package class61To70;

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

// https://www.luogu.com.cn/problem/P4779
public class Dijkstra {
    public static int MAX_N = 100001;

    public static int MAX_M = 200001;

    public static int[] head = new int[MAX_N];

    public static int[] next = new int[MAX_M];

    public static int[] to = new int[MAX_M];

    public static int[] weight = new int[MAX_M];

    public static int cnt;

    public static int n, m, s;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            in.nextToken();
            s = (int) in.nval;
            build(n);
            for (int i = 0; i < m; i++) {
                in.nextToken();
                int u = (int) in.nval;
                in.nextToken();
                int v = (int) in.nval;
                in.nextToken();
                int w = (int) in.nval;
                addEdge(u, v, w);
            }
            int[] ans = compute(s);
            for (int i = 1; i < ans.length; i++) {
                out.print(ans[i] + " ");
            }
        }
        out.flush();
        out.close();
        br.close();
    }

    public static void build(int n) {
        cnt = 1;
        Arrays.fill(head, 0, n + 1, 0);
    }

    public static void addEdge(int u, int v, int w) {
        next[cnt] = head[u];
        to[cnt] = v;
        weight[cnt] = w;
        head[u] = cnt++;
    }

    public static int[] compute(int k) {
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[k] = 0;
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] record = pq.poll();
            int u = record[0];
            if (visited[u]) {
                continue;
            }
            visited[k] = true;
            for (int ei = head[u]; ei > 0; ei = next[ei]) {
                int v = to[ei];
                int w = weight[ei];
                if (distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                    pq.add(new int[]{v, distance[u] + w});
                }
            }
        }
        return distance;
    }
}
